﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;
using EntryEngine;

namespace EntryEngineServer
{
    /// <summary>插件</summary>
    public interface IPlugin : IDisposable
    {
        /// <summary>动态注入插件</summary>
        /// <param name="param">插件注入需要的参数</param>
        /// <returns>新的插件内容，内容具体什么类型用于什么位置</returns>
        object Inject(params object[] param);
    }

    /// <summary>监测和管理插件变化</summary>
    public static class PluginManager
    {
        class WatchFile : IDisposable
        {
            public string Dll;
            public Action<IPlugin> Callback;
            public DateTime LastUpdateTime;
            public Assembly Assembly;
            public IPlugin Plugin;
            /// <summary>依赖的程序集，可能 A 和 B 插件都依赖同一个程序集，则这个程序集也应该互相公用</summary>
            public List<Assembly> References = new List<Assembly>();
            void IDisposable.Dispose()
            {
                list.Remove(this);
                if (list.Count == 0)
                {
                    watcher.Dispose();
                    watcher = null;
                }
            }
        }

        public static string PluginPath = Environment.CurrentDirectory;
        private static FileSystemWatcher watcher;
        private static List<WatchFile> list = new List<WatchFile>();
        private static bool pluginLaunched = false;

        static PluginManager()
        {
            AppDomain.CurrentDomain.AssemblyResolve += (sender, args) =>
            {
                string filepath = args.Name.Substring(0, args.Name.IndexOf(',')) + ".dll";

                // 动态插件之间的互相引用，Assembly.Load 会导致 DLL 不匹配，所以需要保持引用的 dll 一致
                Assembly assembly;

                // 需要加载的 dll
                var watched = list.FirstOrDefault(i => i.Dll == filepath);
                if (watched != null)
                {
                    // 插件间互相依赖
                    if (watched.Assembly != null)
                    {
                        //_LOG.Debug("AssemblyResolve watched exists Dll: {0}", filepath);
                        assembly = watched.Assembly;
                    }
                    else
                    {
                        throw new InvalidOperationException("请保证插件加载顺序符合其依赖顺序");
                    }
                }
                else
                {
                    // 依赖的第三方 dll

                    // 寻找其它插件可能已经依赖了该 dll
                    assembly = list.SelectMany(i => i.References).FirstOrDefault(i => i.FullName == args.Name);
                    if (assembly != null)
                    {
                        //_LOG.Debug("AssemblyResolve refs exists Dll: {0}", filepath);
                    }
                    else
                    {
                        if (File.Exists(Path.Combine(PluginPath, filepath)))
                        {
                            //_LOG.Debug("AssemblyResolve load Dll: {0}", filepath);
                            assembly = Assembly.Load(File.ReadAllBytes(Path.Combine(PluginPath, filepath)));
                        }
                        else
                        {
                            //_LOG.Debug("No plugin in Path: {0}", Path.Combine(PluginPath, filepath));
                        }
                    }
                }

                // 需要 dll 的 dll
                var root = list.FirstOrDefault(i => i.Assembly == args.RequestingAssembly);
                if (root != null && !root.References.Contains(assembly))
                {
                    //_LOG.Debug("AssemblyResolve {0} ref Dll: {1}", root.Dll, filepath);
                    root.References.Add(assembly);
                }

                if (!pluginLaunched && root != null && watched != null)
                {
                    int index = list.FindIndex(i => i == watched);
                    list.RemoveAt(index);
                    index = list.FindIndex(i => i == root);
                    list.Insert(index, watched);
                    //_LOG.Debug("交换位置 {0}", String.Join(",", list.Select(i => i.Dll)));
                }

                return assembly;
            };
        }

        /// <summary>监测一个 dll 文件是否发生变化，并完成首次加载，项目中有多个插件且插件间有依赖，需要自行管理加载顺序</summary>
        /// <param name="dll">dll 文件路径，不能监测同一个 dll 多次</param>
        /// <param name="callback">检测到文件发生变化时的回调，有可能 dll 中有多个插件</param>
        /// <returns>监测实例，可以用来停止监测</returns>
        public static IDisposable Watch(string dll, Action<IPlugin> callback)
        {
            pluginLaunched = false;
            if (list.Count == 0)
            {
                watcher = new FileSystemWatcher(PluginPath);
                watcher.Changed += Watcher_Changed;
                watcher.EnableRaisingEvents = true;
            }
            WatchFile result = new WatchFile()
            {
                Dll = dll,
                Callback = callback,
            };
            list.Add(result);
            HotFixPlugin(result);
            return result;
        }

        /// <summary>首次加载插件，以后是插件的 DLL 变化时才会重新加载插件了</summary>
        //public static void LaunchPlugin()
        //{
        //    foreach (var item in list.ToArray())
        //        HotFixPlugin(item);
        //    // 处理 Watch 的 dll 的依赖顺序，免得每次更新都需要调整顺序
        //    // 但是不加载还真就没法确定顺序，但是此时所有插件都加载完毕过一次了，已经可以确定加载顺序了
        //    // 但是启动之后又调用 Watch 就又需要每次加载重新确定顺序了
        //    pluginLaunched = true;
        //}

        private static void HotFixPlugin(WatchFile item)
        {
            try
            {
                _LOG.Info("更新插件 {0}", item.Dll);
                string pdb = Path.Combine(PluginPath, Path.ChangeExtension(item.Dll, "pdb"));
                item.Assembly = Assembly.Load(File.ReadAllBytes(Path.Combine(PluginPath, item.Dll)), File.Exists(pdb) ? File.ReadAllBytes(pdb) : null);
                foreach (IPlugin plugin in item.Assembly.GetExportedTypes().Where(i => i.GetInterfaces().Contains(typeof(IPlugin))).Select(i => Activator.CreateInstance(i)))
                {
                    using (IPlugin old = item.Plugin)
                    {
                        item.Plugin = plugin;
                        item.Callback(plugin);
                    }
                    break;
                }
            }
            catch (Exception ex)
            {
                _LOG.Error(ex, "更新插件异常");
            }
        }

        private static void Watcher_Changed(object sender, FileSystemEventArgs e)
        {
            if (e.ChangeType != WatcherChangeTypes.Changed)
                return;
            pluginLaunched = true;
            for (int i = 0, c = list.Count; i < c; i++)
            {
                var item = list[i];
                if (e.Name != item.Dll || (DateTime.Now - item.LastUpdateTime).TotalSeconds < 1)
                    continue;

                List<WatchFile> list2 = new List<WatchFile>();
                list2.Add(item);
                //_LOG.Debug("准备更新插件 {0}", item.Dll);
                // 确定插件更新后，哪些插件会一并更新
                for (int j = i + 1; j < c; j++)
                {
                    var item2 = list[j];
                    if (item2.References.Any(n => n == item.Assembly || item.References.Contains(n)))
                    {
                        // 依赖了插件，或者跟插件有相同的依赖
                        //_LOG.Debug("插件{0}更新，依赖其或其相同依赖的插件{1}也重新更新", item.Dll, item2.Dll);
                        list2.Add(item2);
                    }
                }

                foreach (var ii in list2)
                {
                    ii.LastUpdateTime = DateTime.Now;
                    ii.References.Clear();
                }

                ThreadPool.QueueUserWorkItem((_) =>
                {
                    Thread.Sleep(1000);
                    // 热更新后，引用了自己的其它插件也需要重新回调一下
                    foreach (var item2 in list2)
                        HotFixPlugin(item2);
                });
            }
        }
    }
#if SERVER
    /// <summary>
    /// 平衡二叉树
    /// 扩展应用: B+Tree
    ///   节点类型又为一个平衡二叉树（一个节点也叫页），树里的数据一次性通过文件读取到内存，内存数据主要是数据的主键
    ///   硬盘读取数据最小单位也是一页，一页大小为16kb，所以B+Tree的页也可以设置为16kb
    /// </summary>
    public abstract class AVLTreeBase<T> : ICollection<T>
    {
        protected class AVLTreeVisitor
        {
            /// <summary>Find时经过的路径，可以节约AVLTreeNode.Parent的内存</summary>
            public AVLTreeNode[] Path = new AVLTreeNode[32];
            /// <summary>路径长度</summary>
            public int Length;
            /// <summary>0. 找到了目标 / -1. 最后往左没找到目标 / 1. 最后往右没找到目标</summary>
            public sbyte Flag;
            public bool Found { get { return Flag == 0 && Length > 0; } }
            public AVLTreeNode this[int index]
            {
                get
                {
                    if (index < 0 || index >= Length)
                        return null;
                    return Path[index];
                }
            }
            /// <summary>寻找到的目标</summary>
            public AVLTreeNode Target
            {
                get
                {
                    if (Length == 0)
                        return null;
                    return Path[Length - 1];
                }
            }
            public bool IsLeft(int index)
            {
                return Path[index - 1].Left == Path[index];
            }
            public AVLTreeVisitor SetResult(sbyte flag)
            {
                this.Flag = flag;
                return this;
            }
        }
        public class AVLTreeNode
        {
            public byte Height;
            public AVLTreeNode Left;
            public AVLTreeNode Right;
            public T Value;
            public int BalanceFactor
            {
                get
                {
                    int l = Left == null ? -1 : Left.Height;
                    int r = Right == null ? -1 : Right.Height;
                    return l - r;
                }
            }
            public void ResetHeight()
            {
                int l = Left == null ? -1 : Left.Height;
                int r = Right == null ? -1 : Right.Height;
                Height = (byte)((l > r ? l : r) + 1);
            }
            public void CopyTo(AVLTreeNode node)
            {
                node.Height = this.Height;
                node.Left = this.Left;
                node.Right = this.Right;
                node.Value = this.Value;
            }
            public override string ToString()
            {
                return Value == null ? "null" : Value.ToString();
            }
        }
        // 可扩展多个相同的值，此时可以是HashSet，List，或其它
        public class AVLTreeNodeList : AVLTreeNode
        {
            /// <summary>相同键的元素</summary>
            public ICollection<T> Same;
        }

        private int count;
        protected AVLTreeNode root;
        private AVLTreeVisitor visitor = new AVLTreeVisitor();

        public AVLTreeNode Root { get { return root; } }
        public int Count { get { return count; } }
        public int Height { get { return root == null ? -1 : root.Height; } }
        public bool IsReadOnly { get { return false; } }

        public abstract int Compare(T x, T y);
        /// <summary>查找元素</summary>
        /// <param name="item">要查找的目标</param>
        /// <returns>查找结果</returns>
        private AVLTreeVisitor Find(T item)
        {
            visitor.Flag = 0;
            visitor.Length = 0;

            if (root == null)
                return visitor;

            AVLTreeNode node = root;
            int c;
            while (true)
            {
                visitor.Path[visitor.Length++] = node;
                c = Compare(item, node.Value);
                if (c == 0)
                    return visitor.SetResult(0);
                else if (c > 0)
                    // 向右没找到
                    if (node.Right == null) return visitor.SetResult(1);
                    else node = node.Right;
                else
                    // 向左没找到
                    if (node.Left == null) return visitor.SetResult(-1);
                    else node = node.Left;
            }
        }
        protected virtual AVLTreeNode CreateNode()
        {
            return new AVLTreeNode();
        }
        public bool Contains(T item)
        {
            return Find(item).Found;
        }
        /// <summary>将已经升序排好序的对象快速插入以构建树</summary>
        public void SetSortedValuesASC(IList<T> list)
        {
            throw new NotImplementedException();
        }
        /// <summary>将已经降序排好序的对象快速插入以构建树</summary>
        public void SetSortedValuesDESC(IList<T> list)
        {
            throw new NotImplementedException();
        }
        public void Add(T item)
        {
            Insert(item);
        }
        /// <summary>可以添加重复键的节点</summary>
        /// <param name="item">item算出来的键一样，值不一样则插入，否则将调用Update</param>
        public bool Insert(T item)
        {
            if (root == null)
            {
                root = CreateNode();
                root.Value = item;
            }
            else
            {
                var find = Find(item);
                var node = find.Target;
                if (find.Found)
                {
                    // 找到了，替换 | 插入
                    var ret = FindInsert(item, node);
                    if (ret != node)
                    {
                        // 更换节点
                        var parent = find[find.Length - 2];
                        if (parent == null)
                            root = ret;
                        else
                            if (parent.Left == node)
                                parent.Left = ret;
                            else
                                parent.Right = ret;
                    }
                }
                else
                {
                    bool noUncleFlag;
                    AVLTreeNode newNode = CreateNode();
                    newNode.Value = item;
                    visitor.Path[visitor.Length++] = newNode;
                    // 插入时一定是往叶子节点插入，所以高度一定是1
                    node.Height = 1;
                    if (find.Flag > 0)
                    {
                        node.Right = newNode;
                        noUncleFlag = node.Left == null;
                    }
                    else
                    {
                        node.Left = newNode;
                        noUncleFlag = node.Right == null;
                    }

                    // 有叔叔节点时一定平衡
                    if (noUncleFlag && find.Length > 2)
                    {
                        AVLTreeNode child, parent, gparent;
                        int index = find.Length - 1;
                        child = find[index--];
                        parent = find[index--];
                        gparent = find[index];
                        // 重算高度 & 找到失衡节点 & 单次旋转平衡
                        byte height = parent.Height;
                        int b;
                        do
                        {
                            gparent.Height = ++height;
                            b = gparent.BalanceFactor;
                            // 找到失衡节点
                            if (b == -2 || b == 2)
                            {
                                // 旋转平衡
                                ToBalance(child, parent, gparent, find[index - 1]);
                                break;
                            }
                            child = parent;
                            parent = gparent;
                            gparent = find[--index];
                        } while (gparent != null);
                    }
                }
            }
            count++;
            return true;
        }
        /// <summary>通过旋转让树保持平衡</summary>
        /// <param name="gparent">失衡节点</param>
        private void ToBalance(AVLTreeNode child, AVLTreeNode parent, AVLTreeNode gparent, AVLTreeNode ggparent)
        {
            // 左右
            if (parent.Right == child && gparent.Left == parent)
            {
                gparent.Left = child;
                parent.Right = child.Left;
                child.Left = parent;

                byte temp = parent.Height;
                parent.Height = child.Height;
                child.Height = temp;

                RotateRight(gparent, ggparent);
            }
            // 右左
            else if (parent.Left == child && gparent.Right == parent)
            {
                gparent.Right = child;
                parent.Left = child.Right;
                child.Right = parent;

                byte temp = parent.Height;
                parent.Height = child.Height;
                child.Height = temp;

                RotateLeft(gparent, ggparent);
            }
            // 左左
            else if (parent.Left == child && gparent.Left == parent)
                RotateRight(gparent, ggparent);
            // 右右
            else
                RotateLeft(gparent, ggparent);
        }
        private void RotateLeft(AVLTreeNode rotation, AVLTreeNode parent)
        {
            //rotation.Height -= 2;
            var right = rotation.Right;
            if (parent != null)
                if (parent.Left == rotation)
                    parent.Left = right;
                else
                    parent.Right = right;
            rotation.Right = right.Left;
            right.Left = rotation;
            rotation.ResetHeight();
            right.ResetHeight();
            if (parent != null)
                parent.ResetHeight();
            if (rotation == root)
                root = right;
        }
        private void RotateRight(AVLTreeNode rotation, AVLTreeNode parent)
        {
            //rotation.Height -= 2;
            var left = rotation.Left;
            if (parent != null)
                if (parent.Left == rotation)
                    parent.Left = left;
                else
                    parent.Right = left;
            rotation.Left = left.Right;
            left.Right = rotation;
            rotation.ResetHeight();
            left.ResetHeight();
            if (parent != null)
                parent.ResetHeight();
            if (rotation == root)
                root = left;
        }
        /// <summary>插入时找到了相应的节点，默认替换节点</summary>
        /// <param name="item">要插入的键</param>
        /// <param name="node">找到的节点</param>
        protected virtual AVLTreeNode FindInsert(T item, AVLTreeNode node)
        {
            node.Value = item;
            return node;
        }
        /// <summary>更新节点的键，请求重新排序</summary>
        public void Update(T item)
        {
            if (Remove(item))
                Add(item);
        }
        public bool Remove(T item)
        {
            if (root == null) return false;
            var find = Find(item);
            if (find.Found)
            {
                if (DeleteNode(find))
                {
                    int index = find.Length;
                    AVLTreeNode node;
                    // 删除使原本就是短边的树枝变得更加短导致不平衡，相当于另一边树枝插入导致不平衡
                    // 对另一边树枝使用插入相同的算法来维持树平衡
                    // 旋转保持平衡后，可能引起树枝高度变短，从而再次引起不平衡，所以需要一致回溯到根节点，进行多次旋转
                    int b;
                    // 变短需要一直回溯向上更新节点高度
                    while (index > 0)
                    {
                        // 向上回溯 & 更新高度
                        index--;
                        node = find.Path[index];
                        node.ResetHeight();
                        b = node.BalanceFactor;
                        if (b == -2)
                        {
                            // 左边矮，相当于右边插入，向右寻找旋转方案
                            var parent = node.Right;
                            var child = parent.BalanceFactor > 0 ? parent.Left : parent.Right;
                            // 旋转
                            ToBalance(child, parent, node, find[index - 1]);
                        }
                        else if (b == 2)
                        {
                            // 右边矮，相当于左边插入，向左寻找旋转方案
                            var parent = node.Left;
                            var child = parent.BalanceFactor < 0 ? parent.Right : parent.Left;
                            // 旋转
                            ToBalance(child, parent, node, find[index - 1]);
                        }
                    }
                }
                return true;
            }
            return false;
        }
        /// <summary>
        /// 删除节点，有些情况不需要通过旋转来保持树平衡
        /// <para>不需要平衡</para>
        /// <para>1. 对于同值单一节点</para>
        /// <para>2. 删除节点的左右树枝平衡（非叶子节点），即删除完后，无论左还是右代替其原位置，整棵树高度不变</para>
        /// <para>需要平衡</para>
        /// <para>1. 短边删除，导致父级直接失衡</para>
        /// <para>2. 长边删除，父级虽然平衡，但整条边可能变短，引起上层的不平衡</para>
        /// </summary>
        /// <returns>是否需要通过旋转保持平衡</returns>
        protected virtual bool DeleteNode(AVLTreeVisitor visitor)
        {
            count--;
            if (count == 0)
            {
                root = null;
                return false;
            }
            else
            {
                // 获得要删除的节点，并从路径中移除
                int index = visitor.Length - 1;
                var node = visitor.Path[index];
                var parent = visitor[index - 1];

                // 删除非叶子节点且左右平衡的树，替换节点后高度不变，整棵树任然平衡
                bool balance = node.Left != null && node.Right != null && node.Left.Height == node.Right.Height;

                // 删除节点有左节点时，把左节点中最大的节点替换原节点
                // 删除节点只有右节点时，直接把右节点替换原节点
                if (node.Left != null)
                {
                    // 找到左节点中最大的节点
                    var max = node.Left;
                    while (true)
                    {
                        if (max.Right == null)
                        {
                            // 替换到被删除节点额为止
                            visitor.Path[index] = max;
                            break;
                        }
                        else
                            visitor.Path[visitor.Length++] = max;
                        max = max.Right;
                    }
                    // 替换到原节点
                    if (parent == null)
                        root = max;
                    else if (parent.Left == node)
                        parent.Left = max;
                    else
                        parent.Right = max;
                    // 最大节点被移走，将其父节点的右节点指向其左节点
                    var maxParent = visitor[visitor.Length - 1];
                    if (maxParent != null)
                        maxParent.Right = max.Left;
                    max.Left = node.Left;
                    max.Right = node.Right;
                    // 更新父节点高度
                    //int l = visitor.Length - 1;
                    //while (l >= 0 && visitor.Path[l] != parent)
                    //    visitor.Path[l--].ResetHeight();
                }
                else
                {
                    // 替换到原节点
                    if (parent == null)
                        root = node.Right;
                    else if (parent.Left == node)
                        parent.Left = node.Right;
                    else
                        parent.Right = node.Right;
                }

                if (count < 3) return false;
                return !balance;
            }
        }
        public void Clear()
        {
            root = null;
            count = 0;
        }
        public void CopyTo(T[] array, int arrayIndex)
        {
            if (arrayIndex + count >= array.Length)
                throw new IndexOutOfRangeException();

            foreach (var item in LeftToRight())
                array[arrayIndex++] = item;
        }
        public IEnumerator<T> GetEnumerator()
        {
            return LeftToRight().GetEnumerator();
        }
        public IEnumerable<T> GetOrderBy(bool asc)
        {
            if (asc)
                return LeftToRight();
            else
                return RightToLeft();
        }
        public IEnumerable<T> LeftToRight()
        {
            return LeftToRight(root);
        }
        public IEnumerable<T> RightToLeft()
        {
            return RightToLeft(root);
        }
        private IEnumerable<T> Empty()
        {
            yield break;
        }
        public IEnumerable<T> SmallerThan(T item, bool equals, bool asc)
        {
            var find = Find(item);
            var node = find.Target;
            if (node == null) return Empty();
            if (equals)
                return Left(node, asc);
            else
                return Left(node.Left, asc);
        }
        public IEnumerable<T> BiggerThan(T item, bool equals, bool asc)
        {
            var find = Find(item);
            var node = find.Target;
            if (node == null) return Empty();
            if (equals)
                if (asc)
                    return LeftToRight(node);
                else
                    return RightToLeft(node);
            else
                if (asc)
                    return LeftToRight(node.Left);
                else
                    return RightToLeft(node.Left);
        }
        private IEnumerable<T> LeftToRight(AVLTreeNode node)
        {
            if (node == null) yield break;
            if (node.Left != null)
                foreach (var item in LeftToRight(node.Left))
                    yield return item;
            yield return node.Value;
            if (node.Right != null)
                foreach (var item in LeftToRight(node.Right))
                    yield return item;
        }
        private IEnumerable<T> RightToLeft(AVLTreeNode node)
        {
            if (node.Left != null)
                foreach (var item in LeftToRight(node.Left))
                    yield return item;
            yield return node.Value;
            if (node.Right != null)
                foreach (var item in LeftToRight(node.Right))
                    yield return item;
        }
        private IEnumerable<T> Left(AVLTreeNode node, bool asc)
        {
            if (node == null) yield break;
            if (asc)
            {
                int height = node.Height;
                AVLTreeNode[] path = new AVLTreeNode[height + 1];
                path[0] = node;
                for (int i = 1; i <= height; i++)
                {
                    node = node.Left;
                    if (node != null)
                        path[i] = node;
                    else
                        break;
                }
                if (path[height] == null)
                    height--;
                for (int i = height; i >= 0; i--)
                    yield return path[i].Value;
            }
            else
            {
                while (node != null)
                {
                    yield return node.Value;
                    node = node.Left;
                }
            }
        }
        private IEnumerable<T> Right(AVLTreeNode node, bool asc)
        {
            if (node == null) yield break;
            if (asc)
            {
                while (node != null)
                {
                    yield return node.Value;
                    node = node.Right;
                }
            }
            else
            {
                int height = node.Height;
                AVLTreeNode[] path = new AVLTreeNode[height + 1];
                path[0] = node;
                for (int i = 1; i <= height; i++)
                {
                    node = node.Right;
                    if (node != null)
                        path[i] = node;
                    else
                        break;
                }
                if (path[height] == null)
                    height--;
                for (int i = height; i >= 0; i--)
                    yield return path[i].Value;
            }
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        //public void Draw(string output)
        //{
        //    int depth = Height + 1;
        //    int w = (int)Math.Pow(2, depth);
        //    int height = 50;
        //    int y = 10;
        //    using (Bitmap bitmap = new Bitmap(w * height, depth * height + y * 2))
        //    {
        //        using (Graphics g = Graphics.FromImage(bitmap))
        //        {
        //            Font font = new Font("黑体", 12);

        //            Action<int, int, int, AVLTreeNode> draw = null;
        //            draw = (_x, _y, _w, node) =>
        //            {
        //                if (node == null) return;
        //                if (node.Left != null)
        //                    g.DrawLine(Pens.Red, _x, _y, _x - (_w >> 1), _y + height);
        //                if (node.Right != null)
        //                    g.DrawLine(Pens.Red, _x, _y, _x + (_w >> 1), _y + height);
        //                int __x = _x - (height >> 1);
        //                int __y = _y - (height >> 1);
        //                g.FillEllipse(Brushes.Black, __x, __y, height, height);
        //                string text = node == null ? "Null" : node.ToString();
        //                var size = g.MeasureString(text, font);
        //                g.DrawString(text, font, Brushes.White,
        //                    _x - ((int)size.Width >> 1),
        //                    _y - ((int)size.Height >> 1));
        //                g.DrawString(node.Height.ToString(), font, Brushes.Red, _x, _y);

        //                draw(_x - (_w >> 1), _y + height, _w >> 1, node.Left);
        //                draw(_x + (_w >> 1), _y + height, _w >> 1, node.Right);
        //            };

        //            draw((bitmap.Width >> 1), y + (height >> 1), (bitmap.Width >> 1), root);
        //        }
        //        bitmap.Save(output);
        //    }
        //}
    }
    public class AVLTreeSimple<T> : AVLTreeBase<T> where T : IComparable<T>
    {
        public override int Compare(T x, T y)
        {
            return x.CompareTo(y);
        }
    }
    public class AVLTree<T> : AVLTreeBase<T> where T : class
    {
        private Comparison<T> comparer;
        private Func<ICollection<T>> sameElementList;

        public AVLTree() : this(Comparer<T>.Default.Compare) { }
        public AVLTree(Func<T, int> comparer) : this((x, y) => comparer(x) - comparer(y)) { }
        public AVLTree(IComparer<T> comparer) : this(comparer.Compare) { }
        public AVLTree(Comparison<T> comparer)
        {
            if (comparer == null)
                throw new ArgumentNullException("比较器不能为空");
            this.comparer = comparer;
        }

        public override int Compare(T x, T y)
        {
            if (x == y) return 0;
            return comparer(x, y);
        }
        /// <summary>相同键的元素将用集合来存储，这里指定使用哪种集合类（只能指定一次）</summary>
        /// <param name="func">返回集合的新实例</param>
        public void SetSameElementList(Func<ICollection<T>> func)
        {
            if (sameElementList != null)
                throw new InvalidOperationException("不能重复指定集合类型");
            this.sameElementList = func;
        }
        protected override AVLTreeNode FindInsert(T item, AVLTreeNode node)
        {
            if (sameElementList == null || node.Value == null)
            {
                node.Value = item;
                return node;
            }
            else
            {
                AVLTreeNodeList list = node as AVLTreeNodeList;
                if (node == null)
                {
                    node.CopyTo(list);
                    list.Same = sameElementList();
                }
                list.Same.Add(item);
                return list;
            }
        }
        protected override bool DeleteNode(AVLTreeBase<T>.AVLTreeVisitor visitor)
        {
            return base.DeleteNode(visitor);
        }
    }
#endif
}
